//
//  ProblemOffer33.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 33. 二叉搜索树的后序遍历序列
 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

  

 参考以下这颗二叉搜索树：

      5
     / \
    2   6
   / \
  1   3
 示例 1：

 输入: [1,6,3,2,5]
 输出: false
 示例 2：

 输入: [1,3,2,6,5]
 输出: true
  

 提示：

 数组长度 <= 1000
 */
@objcMembers class ProblemOffer33: NSObject {
    func solution() {
        print(verifyPostorder([1,6,3,2,5]))
        print(verifyPostorder([1,3,2,6,5]))
        
        print(verifyPostorder([1,2,5,10,6,9,4,3]))
        print(verifyPostorder([5, 2, -17, -11, 25, 76, 62, 98, 92, 61]))
    }
    
    /*
     5, 2, -17, -11, 25
     5, 2, -17, -11
     
     76, 62, 98, 92
     */
    /*
     二叉搜索树：左 < 根 < 右
     递归
     */
    func verifyPostorder(_ postorder: [Int]) -> Bool {
        return verifyPostorderDFS(postorder, 0, postorder.count-1)
    }
    
    func verifyPostorderDFS(_ postorder: [Int], _ start: Int, _ end: Int) -> Bool {
        if start >= end {
            return true
        }
        
        var right = -1
        for i in start..<end {
            if right == -1 && postorder[i] > postorder[end] {
                right = i
            }
            if right != -1 && postorder[i] < postorder[end] {
                return false
            }
        }
        if right == -1 {
            right = end
        }
        
        let l = verifyPostorderDFS(postorder, start, right-1)
        if l == false {
            return false
        }

        let r = verifyPostorderDFS(postorder, right, end-1)
        if r == false {
            return false
        }
        
        return true
    }
}
